/* 
 * Word Ladder
 * start = "hit" end = "cog" dict = ["hot", "dot", "dog", "lot", "log"]
 * hit->hot->dot->dog->cog
 */

#include "../func.h"

static auto speedup = [](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dict(wordList.begin(),wordList.end()), head, tail, *pHead, *pTail;
        
        if(dict.find(endWord) == dict.end())    //没找到这个单词
            return 0;
        
        head.insert(beginWord);
        tail.insert(endWord);
        
        int ladder = 2;
        
        while(!head.empty() && !tail.empty()){
            //让pHead指向长度较小的set，用于遍历
            //让pTail指向长度较大的set，用于搜索
            if(head.size() < tail.size()){
                pHead = &head;
                pTail = &tail;
            }
            else{
                pHead = &tail;
                pTail = &head;
            }
            unordered_set<string> tmp;
            for(auto it = pHead->begin();it!=pHead->end();it++){
                string word = *it;
                for(int i = 0;i<word.size();i++){
                    //依次更改word中的字符，判断是否在dict中
                    char origin = word[i];
                    for(int j = 0;j<26;j++){
                        word[i] = 'a' + j;  //a~z
                        //两集合相遇，即找到了转换方法
                        if(pTail->find(word) != pTail->end())
                            return ladder;
                        //没相遇，但是当前单词在dict中，则将这个转换加入候选以供下一次寻找
                        if(dict.find(word) != dict.end()){
                            tmp.insert(word);
                            dict.erase(word);   //已经遍历过dict中的单词，需要删除
                        }
                     }
                    word[i] = origin;   //恢复，以供下一个字符变化的遍历
                }
            }
            ladder++;
            pHead->swap(tmp);   //swap是替换，将当期head换为tmp
        }
        return 0;
    }
};
